package cn.edu.zufe.mjt.binary;

import cn.edu.zufe.mjt.validator.Validator;

import java.util.Arrays;

/**
 *  二分答案 —— 小塔的地砖
 * <h2>题目内容</h2>
 * 小塔有a个红砖、b个蓝砖和c个绿砖。每x个红砖可以合成1个蓝砖，每y个蓝砖可以合成1个绿砖。
 * 砖块只能正向合成不能反向分解。一套砖块包含1个红砖、1个蓝砖和1个绿砖。请计算小塔最多可以收集多少套砖块。
 * <h2>输入描述</h2>
 * 每个测试文件均包含多组测试数据。第一行输入一个整数T(1 < T < 10^5)代表数据组数，
 * 每组测试数据描述如下:在-行上输入五个整数a,b,c,x,y(0 ≤ a,b,c ≤ 10^9,1 ≤ x,y ≤ 10^9)，分别表示红砖、蓝砖、绿砖的数量及合成的比例。
 *
 * <h2>输出描述</h2>
 * 对于每一组测试数据，在一行上输出一个整数，代表小塔最多可以收集到的砖块套数。
 */
public class FloorTileQuestions {

    public static void main(String[] args) {
        int[] t = new int[5];
        for (int i = 0; i < t.length; i++) { // 随机生成测试数据
            t[i] = Validator.randomArray(1, 20)[0]/(i + 1);
        }
        System.out.println("input: " + Arrays.toString(t));
        System.out.println("output: " + maxFloorTiles(t[0], t[1], t[2], t[3], t[4]));

        System.out.println(maxFloorTiles(1, 2, 3, 4, 2));
        System.out.println(maxFloorTiles(10, 2, 1, 4, 2));
    }

    public static int maxFloorTiles(int a, int b, int c, int x, int y) {
        /* 答案具有单调性：
         I 答案 min(num(a),num(b),num(c))
         II 单调性：min(num(a),num(b),num(c)) 越大，越难达成

         转化为数组问题：
         [√，√，√，×，×]
         [1,2,3,4,5]  P[i] 表示套数为i是否可行，那么当 min = mid 可行时，L = mid+1，否则 R = mid-1。
         如何检查 min = v 是否可行？ 贪心：
         在保证红砖 不小于 v 的情况下合成蓝砖， nb = b + (a-v)/x，然后在保证蓝砖不小于 v 的情况下合成绿砖， nc = c + (nb-v)/y
         这时 nc 是否 大于等于 v 就决定了是否可行，因为前两步已经保证了 a 和 b 都不小于 v。*/
        int l = 1; // 最小砖块数
        int r = a + b + c; // 最大套数，也可以是 min(a,b,c)
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (checkValue(mid, a, b, c, x, y)) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r;

    }

    private static boolean checkValue(int value, int a, int b, int c, int x, int y) {
        if (a < value) { // 红砖不够
            return false;
        }
        int nb = b + (a - value) / x;
        if (nb < value) { // 蓝砖不够
            return false;
        }
        int nc = c + (nb - value) / y;
        System.out.println("checkValue: " + value + " na：" + (a-value) +  " nb：" + nb + " nc：" + nc);
        return nc >= value; // 绿砖够不够
    }
}
